package site.wanjiahao.back_tracking;

/**
 * N皇后问题
 *      使用回溯＋剪枝处理
 */
public class Queens {

    // 存放某个皇后的摆放位置
    private int cols[];

    private int size;

    public Queens(int size) {
        if (size <= 1) return;
        cols = new int[size];
    }

    // 摆放皇后
    public void place() {
        // 从第一个元素开始摆放
        place(0);
        System.out.println("共有" + size + "种摆法");
    }

    public void place(int row) {
        // 确定递归基
        if (row >= cols.length) {
            // 成功确定一次摆放位置
            size++;
            // 展示当前摆放，详情
            show();
            return;
        }
        // 遍历列，确定那个位置摆放皇后
        for (int col = 0; col < cols.length; col++) {
            // 如果可以摆放，则摆放
            if (isPlace(row, col)) {
                cols[row] = col;
                // 递归调用下一个元素摆放，当此函数弹出，将会自动执行回溯操作
                place(row + 1);
            }
        }
    }

    private void show() {
        int len = cols.length;
        for (int col : cols) {
            for (int j = 0; j < len; j++) {
                if (col == j) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("--------------------------");
    }

    private boolean isPlace(int row, int col) {
        // 确定当前位置是否可以摆放皇后
        for (int i = 0; i < row; i++) {
            // 如果出入同一列，者不能摆放
            if (col == cols[i]) return false;
            // 如果出入同一个对角线，者也不能摆放
            if (row - i == Math.abs(col - cols[i])) return false;
        }
        return true;
    }


}
